Context Free Grammar
Q1.
Consider the context-free grammar G below S\rightarrow aSb \;| \;X X\rightarrow aX \;| \;Xb \;|\; a\;|\; b where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S. Which one of the following statements is CORRECT?Q2.
If G is grammar with productions S\rightarrow SaS|aSb|bSa|SS|\epsilon where S is the start variable, then which one of the following is not generated by G?Q3.
Consider the following context-free grammar where the set of terminals is \{a,b,c,d,f\}.\begin{array}{lll} S & \rightarrow & d \: a \: T \mid R \: f \\ T & \rightarrow & a \: S \: \mid \: b \: a \: T \: \mid \epsilon \\ R & \rightarrow & c \: a \: T \: R \: \mid \epsilon \end{array} The following is a partially-filled LL(1) parsing table. Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?Q4.
Consider the following grammar. P\rightarrowxQRS Q\rightarrowyz|zR\rightarroww|\varepsilon S\rightarrowyWhat is FOLLOW (Q) ?Q5.
The language which is generated by the grammar S \rightarrow a S a\mid b S b\mid a\mid b over the alphabet of {a,b} is the set ofQ6.
Which of the following languages is generated by the given grammar? S\rightarrow aS|bS|\varepsilonQ7.
Consider the following statements about the context free grammarG=\{S \rightarrow S S, S \rightarrow a b, S \rightarrow b a, S \rightarrow \epsilon\}I. G is ambiguous II. G produces all strings with equal number of a's and b's III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G?Q9.
Consider the following context-free grammar over the alphabet \sum = {a,b,c} with S as the start symbol. S\rightarrowabScT|abcT T\rightarrowbT|b Which one of the following represents the language generated by the above grammar ?Q10.
Consider the following expression grammar G: E\rightarrowE-T|T T\rightarrowT+F|F F\rightarrow(E)|id Which of the following grammars is not left recursive, but is equivalent to G?